package leetcode_ago.sort;

/**
 * @author 美女
 * @date 2022/03/21 19:23
 * 给定链表的头结点head，请将其按升序排列并返回排序后的链表
 **/

/**
 * 利用归并排序的merge方法：先把大链表拆成一个小链表，再将小链表组合回一个升序的大链表
 * 拆分时找链表中间点：快慢指针
 * 合并两个升序链表：见leetcode21
 */
public class Num148_SortList {
    private static class ListNode {
      int val;
     ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 }
    public static ListNode sortList(ListNode head) {
        return sortListHelper(head,null);
    }
    //拆分链表
    private static ListNode sortListHelper(ListNode head, ListNode tail) {
        if(head==null){
            return head;
        }
        if(head.next==tail){
            head.next=null;
            return head;
        }
        //找到链表中间点：快慢指针
        ListNode slow=head;
        ListNode fast=head;
        while (fast!=tail){
            fast=fast.next;
            slow=slow.next;
            if(fast!=tail){
                fast=fast.next;
            }
        }
        //此时找到了链表的中间节点
        ListNode mid=slow;
        //拆分左侧链表
        ListNode leftList=sortListHelper(head,mid);
        //拆分右侧链表
        ListNode rightList=sortListHelper(mid,tail);
        //此时链表拆分完毕，进行merge操作合并链表
        return merge(leftList,rightList);
    }

    private static ListNode merge(ListNode leftlist, ListNode rightlist) {
        //合并两个链表（升序）;返回合并后的链表
        if(leftlist==null){
            return leftlist;
        }
        if(rightlist==null){
            return rightlist;
        }
        //此时两个链表都不为空，进行两个链表的合并操作
        //创建虚拟头节点，使用尾插进行插入
        ListNode dummyHead=new ListNode(10*10*10*10*10+1);
        ListNode cur=dummyHead;
        while (leftlist!=null&&rightlist!=null){
            if(leftlist.val<=rightlist.val){
                cur.next=leftlist;
                cur=leftlist;
                leftlist=leftlist.next;
            }else{
                cur.next=rightlist;
                cur=rightlist;
                rightlist=rightlist.next;
            }
            //判断left与right是否遍历到空
            if(leftlist==null){
                cur.next=rightlist;
            }
            if(rightlist==null){
                cur.next=leftlist;
            }
        }
        return dummyHead.next;
    }

    public static void main(String[] args) {
        ListNode node1=new ListNode(-1);
        ListNode node2=new ListNode(5);
        ListNode node3=new ListNode(3);
        ListNode node4=new ListNode(4);
        ListNode node5=new ListNode(0);
        node1.next=node2;
        node2.next=node3;
        node3.next=node4;
        node4.next=node5;
        ListNode res=sortList(node1);
        System.out.println(res);
    }
}
